Given an array with elements
Compute the sum of every possible subarray and store the maximum.
The complexity is given by the two nested for loops
Kadane's Algorithm is based on two observations:
kadane_algorithm(a[])
n = a.length()
max = Integer.MIN_VALUE
sum = 0
for i = 0 to n
if sum > 0
sum += a[i]
else
sum = a[i]
max = Math.max(sum, max)
return max
Example:
Given an array n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
For each element find the highest bar to its left and right. Take the smaller of the two bars and call it
The point is to think locally, not globally.
We compute two support arrays, the array of left and right leaders.
An element of an array is a right leader if it is greater than or equal to all the elements to its right side. The rightmost element is always a leader. Left leaders are analogous.
Computing leaders cost
We then have that:
The water that can be stored over the element
Idea based on the previous solution plus the observation that we do not need all the leaders, but just the two currently meaningful leaders.
max_water(heights[])
n = heights.length()
left = 0, right = n-1
result = 0
left_max = 0 // max height seen by "left" so far, curr LL
right_max = 0 // max height seen by "right" so far, curr RL
while left < right
if heights[left] < heights[right] // shift "left"
if heights[left] > left_max
left_max = heigths[left] // cant store water
else
// add to the result the amount of warer
// that can be kept over the position left
result += left_max - heights[left]
left += 1
else // shift right
if heights[right] > right_max
right_max = heights[right] // cant store water
else
result += right_max - heights[right]
right -= 1
return result
Divide-and-conquer algorithm that searches an element within a sorted array:
binary_search(a[], target)
n = a.length()
low = 0
high = n - 1
while low < high
mid = low + (high - low) / 2
if a[mid] == target
return mid
if a[mid] < target
low = mid + 1
else
high = mid
return -1
We can use BS to return the first (or last) occurrence of the element by modifying the first if:
if a[mid] == target
answer = mid
high = mid
We can binary search the answer of a problem if:
[low, high]pred that is true if the answer is good for our aimsMonotone Boolean Predicate: the predicate true to false at most once as
This monotonicity makes it possible to use binary search to efficiently find the boundary where the predicate changes its value from true to false.
If no assumption is done on pred we have no other way than evaluating pred on every element inside [low, high], hence complexity of
But if the predicate is monotone we can binary search the answers in [low, high].
Say that we want the biggest possible answer, then:
rangeBS(low, high, pred)
answer = -1
while low < high
mid = low + (high - low) / 2
if pred(mid) == true
answer = mid
low = mid+1 // we want the biggest
else
high = mid
return answer
We have a non-negative integer
We can use the previous approach as:
Hence we can simply call rangeBS(0, v, p) and return the smallest element that verifies the predicate.
Consider a sequence of
The extremes of each interval are non-negative integers.
We aim to find
If a certain distance is feasible (i.e., exists a selection of points at that distance), then any smaller distance is also feasible. The feasibility is a monotone boolean predicate.
As the candidate answers range from
What's the cost of evaluating the predicate?
We sort the intervals by their left endpoints and then evaluate any candidate distance
by scanning the sorted intervals from left to right.
First we select the left extreme of the first interval as the first point.
Then we move over the intervals and we choose greedily points at a distance at least
Thus an evaluation of the predicate takes
The total running time is
pred(intervals, distance, c) {
// the first point is the start of the first interval
lastSelected = intervals[0].start
counter = 1
// for every interval in intervals
for i in intervals
// we select as many points as we can in every interval.
// we get the max using i.start because if a point falls
// in the empty space between two intervals we place it
// at the start of the current interval
while Math.max(lastSelected + distance, i.start) <= i.end
lastSelected = Math.max(lastSelected + distance, i.start)
counter++
// returns true if we placed at least c points
return counter >= c
}
socialDistancing(intervals, c) {
// l is the maximum length of an interval
if l < c
return -1 // there is no solution
// sort the intervals by the start
intervals.sort()
// do a tailored rangeBS on all the candidate answers
// for each of them compute the predicate
rangeBS(1, l+1, pred)
}
A peak element is an element strictly greater than its two neighbors.
Given an integer array nums of
Mind that
Write an algorithm that solves the problem in
We use a binary search approach to solve the problem.
If the element in the middle is smaller than its right neighbor than the right neighbor could be a peak, and we do low = mid + 1 to proceed the search in the right side of the array.
Otherwise we do the opposite.
peak_elements(a[])
n = a.length()
low = 0
high = n - 1
while low < high
mid = low + (high - low) / 2
if a[mid] < a[mid + 1]
low = mid + 1
else
high = mid
return low
This solution works because a peak is guaranteed to be found (as a last resource, in the first or last element of the array).
Tree traversals are a form of graph traversal and refers to the process of visiting each node in a tree data structure exactly once.
Such traversals are classified by the order in which the nodes are visited.
Traversing a tree involves iterating over all the nodes in some manner.
Since from a given node there is more than one possible next node some nodes must be deferred, aka stored, in some way for later visiting. This is often done via a stack (LIFO) or queue (FIFO).
As a tree is a recursively defined data structure, traversal can be defined by recursion.
In these cases the deferred nodes can be implicitly stored in the call stack.
In DFS the search tree is deepened as much as possible before going to the next sibling.
To traverse a binary tree with DFS we perform the following operations on each node:
The choice of the order of N, L, R determines the color and the type of visit:
Complexity Analysis:
Given a binary tree u.
// returns the size of the subtree rooted in u
subtree(u)
if u == null
return 0
l = subtree(u.left)
r = subtree(u.rigth)
return l + r + 1
The idea is that the information is flowing bottom-up, as the size of an empty node is known (the size of tree rooted in a leaf) and with that info from the bottom you build up the solution for the upper nodes.
Given a binary tree u, where the depth of a node is defined as the distance from the root.
depth(u, d)
if u == null
return
depth(u.left, d+1)
print(u, d)
depth(u.right, d+1)
The information is flowing top-down.
To print the depth of every node you simply call depth(r, 0), where r is the root.
Given a tree u such that the sum of keys on the path root-to-u equals the sum of the keys in u's subtree.
// u is the target node, psum is the path sum so far from r to u
// this function returns a pair:
// - counter (number of nodes that satisfy pathsum == treesum)
// - subtree sum: the sum of the subtree rooted in u
// the initial call of this function will be pathSubtreeSum(r, 0)
pathSubtreeSum(u, psum)
if u == null
return 0,0
// cl / cr = counter left / counter right
// sl / sr = left subtree sum / right subtree sum
cl, sl = pathSubtreeSum(u.left, psum+u.k)
cr, sr = pathSubtreeSum(u.right, psum+u.k)
// sum subtree rooted in u
su = sl + sr + u.k
// counter subtree rooted in u
cu = sl + sr
// is u a node such that the sum of its subtree
// is equal to the sum of the keys on its path to the root?
if su == psum
cu = cu + 1 // also count u as a node that respect the property
return cu, su
Given a binary tree, find the maximum sum path from a leaf to the root.
Example: consider the following binary tree:
10
/ \
-2 7
/ \
8 -4
Since we have three leaves (
The sum of these paths are
Therefore the maximum sum leaf-to-root path is the last one:
The solution is made of the following two steps:
The following snippet clarifies the process:
maxPathSum = MIN
targetLeaf = null
maxLeafRootPath(root)
targetLeaf = findTargetLeaf(root, 0)
print maxPathSum
// set targetLeaf to the leaf with maximum sum leaf-to-root path
findTargetLeaf(node, currentPathSum)
if node == null
return
// compute the current path sum from root to this node
currentPathSum += node.value
// the current node is a leaf
if node.isLeaf == true
// this leaf has the maximum sum leaf-to-root
// path so far: store the leaf and save the sum
if currentPathSum > maxPathSum
maxPathSum = currentPathSum
targetLeaf = node
// this node is not a leaf: recur on children
findTargetLeaf(node.left, currentPathSum)
findTargetLeaf(node.right, currentPathSum)
Time Complexity
The time complexity of the above solution is
Given a binary tree find the maximum path sum from a leaf to another.
Example:
The obvious approach is to reuse the solution of the problem seen before.
For every node x we compute:
x.left-to-leaf pathx.right-to-leaf pathxFor every node x we call twice maxLeafRootPath. Since the function cost
We can find the maximum sum using a single traversal of binary tree.
The idea is to maintain two values in every recursive call:
To solve the problem we use a custom post-order visit maxPathSum that exploits a global variable maxSum to store the result.
Our visit maxSumPath receive in input the root of the tree and then
null we return left = maxSumPath(root.left), we recur on the left subtreeleft is the path sum from the current node to a leafright = maxSumPath(root.right), we recur on the right subtreemaxSum = Math.max(left+right+root.value, maxValue), update the maxSum if we found a bigger path from leaf to leaf passing for the current nodeThe following snippets further clarifies the algorithm:
maxValue = 0
solution(root)
maxPathSum(root)
print(maxValue)
// calculates two things:
// 1) maximum path sum between two leaves, which is stored in maxValue.
// 2) max current-node-to-leaf path sum, which is returned.
maxPathSum(node)
if node == null
return 0
left = maxPathSum(node.left)
right = maxPathSum(node.right)
maxValue = Math.max(maxValue, left+right+node.value)
return Math.max(left, right) + node.value
In "one pass" (aka one traversal) we do what we did in the trivial solution.
The reasoning is the following:
xx.left to a leaf i and the max sum path from x.right to a leaf j.i to j, that passes through x, is greater than the one previously stored? Then we update the maxThe result is maxValue when the program terminates.
Given a sorted array and an integer x, find if there exists any pair of elements a[i], a[j] such that x = a[i] + a[j]
Scan the array twice and we return true if we find two numbers that adds up to x
pairSum(a[], x)
n = a.length()
for i = 0 to n
for j = i+1 to n
if a[i] + a[j] == x
return true
if a[i] + a[j] > x
break // a is sorted, need a new "i"
return false
We use two pointers, left and right, to find the solution.
The pointer left will point to the first element of the array, and right to the last.
If the sum of the elements pointed by left and right is greater than x we will shift backwards by one right, in the other case we shift left one position to the right.
The solution takes advantage of the sortedness of the array.
pairSum(a[], x)
n = a.length()
left = 0, right = n-1
while left < right
if a[left] + a[right] == x
return true
if a[left] + a[right] < x
left++
else
right++
return false
A Binary Search Tree (BST) is a rooted binary tree data structure where each node's key is bigger than all the keys stored in the node's left subtree, and smaller than all the keys stored in the node's right subtree.
Since the nodes in a BST are laid out so that each comparison skips about half of the remaining tree, the lookup takes
The same goes for the other two operations: insertion and removal.
In the worst case (keys are descending or ascending values) a BST degrade to that of a singly linked list:
This actually never happen in reality as it is always used a Balanced BST (BBST): if you have a sorted array that would make a skewed BST simply select the median element as the root of the tree.
In this notes when we say BST we actually mean a BBST.
Searching for a specific key can be done recursively or iteratively.
For certain operations, given a node
Assuming that all the keys of the BST are distinct, the successor of a node
On the other hand, the predecessor of a node
Said Easy:
Predecessor and Successor takes
Removing an element from a BST costs
Check if the binary tree
We remember the property that a binary search tree has to respect:
// returns false if any node in u's subtrees don't respect the property
checkBST(u)
if u == null
return true
bL = checkBST(u.left) // is the left child a BST?
bR = checkBST(u.right) // is the right child a BST?
maxL = maxTree(u.left) // max element in the left subtree
minR = minTree(u.right) // min element in the right subtree
bU = maxL <= u.k && minR > u.key // u respect the property?
return bL && bR && bU
maxTree(u)
if u = null
return MIN // return -infinite
mL = maxTree(u.left)
mR = maxTree(u.right)
return max(mL, mR, u.k)
This solution works but it is too slow as for every node i of the subtree rooted in u we check if the subtree rooted in i respect the property.
We do a lot of repeated work.
In the worst case, (a skewed BST (therefore a non balanced BST)) the cost to pay is
We build upon the previous solution
// return false if any node do not respect the property
checkBST(u)
if u == null
// (is a BST, max and min in the subtree)
return true, MAX, MIN
bL, maxL, minL = checkBST(u.left)
bR, maxR, minR = checkBST(u.rigth)
bU = maxL <= u.k && minR > u.key // u respect the property?
return (bL && bR && bU), max(u.k, maxL, maxR), min(u,k, minL, minR)
Given a set
insert(x)delete(x)lookup(x), is x in min/maxpredecessor(x): x may not be in successor(x): x may not be in With BBST all the operations are solved in
Insertions, search and retrieving the min/max are quite obvious (with the catch of balancing when we insert in the tree).
The other operations are a bit trickier.
TODO
There are
For each frog we have two values:
We then have
For each mosquito we have two values:
Frogs and mosquitoes are represented as points on the coordinate axis.
The frog can eat a mosquito if the mosquito is in the same position with the frog or to its right, and the distance between them is not greater than the length of the tongue of the frog.
If at some moment several frogs can eat a mosquito the leftmost frog will eat it (with minimal
After eating a mosquito the length of the tongue of a frog increases with the value of the size of the eaten mosquito.
It's possible that after it the frog will be able to eat some other mosquitoes: the frog should eat them in this case.
A mosquito is landing to the coordinate axis only after the frogs eat all possible mosquitoes landed before.
Mosquitoes are given in order of their landing to the coordinate axis.
For each frog print two values: the number of eaten mosquitoes and the final length of the tongue.
The target complexity is
We store the position of the frogs in a BST.
When a mosquito lands on position b, to know which frog eats it we simply do a predecessor(b) query on the frog tree.
This base solution needs to be adjusted to account for three main issues:
(p, p+tongue). To enforce that the leftmost frog has the priority on the landing mosquito we preprocess the input segments to force no overlap. If two frogs share a common segment the rightmost frog gets moved and we assign to it assigned the segment (r+1, r+1+tongue) where r is the maximum distance reached by the tongue of the left frog. If a frog segment is contained by another frog then that frog is removed entirely.Time Complexity:
We have
Forcing no overlap in the starting segments takes
Predecessor queries:
Changing dynamic segments:
Then the overall time complexity is dominated by
And we see that
The above operations can be made as
Space Complexity:
Given an array a[0, n-1] and an integer k find the maximum for each subarray, aka window, of a of size k.
The trivial approach is to consider each of the n-k+1 windows independently.
For each window we compute its maximum by scanning it completely, which takes
We do that for each element of the array, hence
The problem in this approach is that we do not use the result of previous windows to compute the maximum of the current one.
To solve efficiently this problem we need a data structure that handle the next window while using the progress made in processing the previous one.
Notice that:
k. In this setting the result for the current window is simply the biggest element in We then require a data structure capable of performing three operations on a (multi)set:
A BBST supports the three operations in
We can then solve the problem in
k elements of the array in the tree and store the maximumA heap is a tree-based data structure that satisfy the heap property:
C, if P is a parent of C than the key of P is CP is CThe main operations of a heap are:
The solution can be then found using a max-heap and scanning through the array left to right:
k elements, along with their respective positionsWe insert elements with their respective index so that we can now if it is part of the window or not.
If the index of an element in the tree is smaller than i - (k-1), where i is the current iteration index, then the element is outside the window.
Using the above approach we have n insertions and at most n extractions of the maximum (window of size
Since the maximum number present in the heap at any given time is up to n, each of these operations takes
The overall complexity is
The BST solution can do more than what is requested, e.g. we can have the second largest element in the window.
The fact that we can do much more than what is requested, it’s an important signal to think that a faster solution could exist.
The best solution uses a deque, a double-ended queue, which supports constant time insertion, removal and access at the front and back of the queue.
The algorithm behaves as follows:
Q that store only elements that are relevant for the current window. Specifically: Q stores only elements that are maximum candidates for the current and for future windows.Q that are outside the current window. This is done by checking if the indices of those elements are beyond the current window boundaryQ that are Q, as it could be a maximum element in the current or future windows// q = [a, ..., z]
// front back
// head tail
slidingWindowMaximum(a[])
n = a.length()
Deque q
maxs[n-k+1]
// first window
for i = 0 to k
while !q.isEmpty() && a[i] > a[q.back()]
q.popBack()
q.pushBack(i)
maxs.push(a[q.front()]);
for i = k to n
// remove elements that dont belongs in the window
while !q.isEmpty() && q.front() + k <= i
q.popFront()
// remove elements that are smaller that the current element
// as this elements cannot be the maximum for this window nor
// for future windows
while !q.isEmpty() && a[i] > a[q.back()]
q.popBack()
q.pushBack(i)
maxs.push(a[q.front()])
return maxs;
The correctness of the algorithm is based on two theorems:
1) Theorem: The elements in Q are sorted in decreasing order.
Proof: we prove the theorem by induction on the number of iterations.
Q is empty, trueQ after i iterations. By inductive hypothesis Q is sorted. The current iteration i+1 will remove elements only from the front and the back of the deque, hence no change in the order of elements. Then we insert the current element a[i+1] as the tail of Q, just after an element that is strictly greater than it (if any). Thus the queue remains sorted.We now introduce the definition of right leaders of the window to show that the largest element within the window is at the top (head) of the queue.
Given a window an element is called right leader if and only if it is larger than any other element of the window at its right.
As an example: the red elements are right leaders:
2) Theorem: At every iteration Q contains all and only the right leaders of the current window.
Proof:
Q as all the subsequent elements are smaller than it.Q.Q.Q contains one such element, say 𝑎. Let 𝑟 be the largest right leader. On one hand, 𝑎 cannot be <= 𝑟, otherwise 𝑎 would be removed when inserting 𝑟 in Q. On the other hand, 𝑎 cannot be larger than 𝑟, otherwise, it would be in front of Q and removed by the first inner loop.We derive correctness of the algorithm by combining the sortedness of Q with the fact that the largest leader is the element to report.
We have a loop that is repeated n times.
The cost of an iteration is dominated by the cost (and thus the number) of pops.
However in certain situations we may pop all the elements in the deque.
As far as we know there may be up to n elements in the deque and thus an iteration may cost
The above analysis is wrong.
It is true that there may exist very costly iterations but they are amortized by many cheap ones.
The overall number of pop iterations cannot be larger than n as an element is not considered anymore by the algorithm as soon as it is removed from Q.
Each of them costs constant time, thus the complexity is
The Sweep Line Algorithm is an algorithmic paradigm used to solve a lot of problems in the computational geometry efficiently.
Sweep Line is used to solve problems on a line or on a plane.
The idea is to use an imaginary line sweeping over the x-axis.
As it progresses we maintain a running solution to the problem at hand.
The solution is updated as the vertical line reaches key points where some event happen.
The type of event tells us how to update the solution.
Consider a set of intervals
We say that two intervals
The objective is to compute the maximum number of overlapping intervals.**
Example:
We have a set of
We apply the sweep line approach to the problem.
The idea is to let the line sweep left to right and stop at the beginning or at the end of every interval: the endpoints of the intervals are the meaningful events.
We maintain a counter which keeps track of the number of intervals that are currently intersecting the sweep line, along with the maximum value of the counter.
For each point we first add to the counter the number of intervals that begin at that point, then we subtract the number of intervals that ends at that point.
Observation: the sweep line only touches points on the x-axis where an event occurs.
This is important as the number of considered points, and thus the complexity, is proportional to the number of intervals, and not to the size of the x-axis.
The algorithm behaves as follows:
axis of pairs (p, isStart)p is either isStart is true if p is the start of an interval (aka, a axis by the first element of each paircounter = 0 and max = 0axis using the iteration variable iaxis[i] is the start of an interval (`axis[i].isStart == true)counter++max = Math.max(counter, max)counter--maxConsider a set of n points on a plane.
The goal is to find the closest pair of points in the set.
The distance between two points
We tackle the problem using Sweep Line.
We start by sorting the points in increasing order of their x-coordinate.
We use
Initially
Then we use a vertical sweep line to iterate through the points, attempting to improve
Consider the point
We can improve
If such point exists it must have a x-coordinate in the interval
The following figure shows the rectangle within the point must lie:
There can be at most 6 points within this rectangle.
The 6 circles within the perimeter of this rectangle represents points that are at distance exactly
Four our purpose a slightly weaker result is enough, which states that the rectangle contains at most 8 points.
To understand why lets consider the 8 squares in the figure above.
Each of these squares, including its perimeter, can contain at most one point.
Let's assume that a square contains two points:
The distance between
This is not possible: the value of
Let's use the above intuition to solve the problem.
We build step-by-step a BBST with points sorted by their y-coordinates.
When processing the point
If the current point
This is because the points are sorted by x on the axis: if the point
Else we compute the distance of
Every time we update
Before moving the sweep line to the next point we insert
What is the complexity of the algorithm?
Let's consider the following costs:
The overall complexity is therefore
Consider an array ranges of ranges left and right.
Return true if each integer [left, right] is covered by at least one interval in ranges.
An integer ranges[i] =
Check that every integer x [left, right] is covered by at least one interval in ranges
isCovered(ranges, left, right)
for i = left to right
covered = false // i is not covered until proven otherwise
for range in ranges
if i >= range.start && i <= range.end
covered = true // i is covered by the current interval
break;
// if i is not covered then we return false
if covered == false
return false
// each i in [left, right] is covered by at least one range
return true;
We use sweep line and a map to solve the problem.
isCovered(ranges, left, right)
// map: point i -> number of open ranges in i
HashMap openRangesAt
for range in ranges
openRangesAt.insert(openRangesAt.getOrDefault(range.start, 0) + 1)
// range.end+1 as the ranges are inclusive!
openRangesAt.insert(openRangesAt.getOrDefault(range.end+1, 0) - 1)
openRangesNow = 0
for i = 0 to left
openRangesNow += openRangesNow.getOrDefault(i, 0)
for point=left to right
openRangesNow += openRangesNow.getOrDefault(point, 0)
if openRangesNow == 0
return false
return true
Consider an array of integers.
Let's call a sequence of one or more consecutive elements in the array a segment (aka subarray)
We say that a segment is
Find any longest
Observation: We can use different data structures to solve this problem.
The time complexities are:
The problem has some similarities with Sliding Window Maximum: there you wanted the max element for any window of size
We use two pointers to simulate a dynamic sliding window.
We use a hash-set to store elements
findMaxSegment(a[], k)
n = a.length
left = 0, right = 0 // pointers current window
maxLeft = 0, maxRight = 0 // pointers current longest k-good seg
Set uniques
while left < right
if uniques.size() <= k
uniques.add(a[right])
if uniques.size() <= k && right - left > maxRight - maxLeft
maxRight = right
maxLeft = left
right++
else
uniques.remove(a[left])
left++
return (maxLeft, maxRight)
Why it works?
The key is in the first two ifs.
If uniques.size() <= k we insert the current element a[right]. At this point we have two cases:
uniques.size() has growna[right] is a never-seen-before elementuniques.size() <= k and right - left >= maxRight - maxLeft than this is a new longest k-good segment, and therefore we update maxLeft and maxRightuniques.size() > k this is not a k-good segment and in the next iteration(s) we will remove the tail element a[left] until we return in k-good segment scenariouniques.size() is the same as beforea[right] was seen beforeuniques.size() <= kmaxLeft and maxRightThe prefix sum, also known as cumulative sum, is used to solve a wide range of problems that involve querying cumulative information about a sequence of values or elements.
The essence of prefix sums lies in transforming a given array of values into another array, where each element at a given index represents the cumulative sum of all preceding elements in the original array.
Consider a string
We need to answer
Each query
Consider the following example (
To solve the problem we can use the prefix sums.
We can compute the binary array
Now every query can be solved in constant time by computing the prefix sum array of the vector
Let's call
We are given an array
The goal is to permute the elements in
The key is to observe that if we want to maximize the sum we have to assign the largest values to the most frequently accessed entries.
Hence the solution consists in sorting
Once we have computed the frequencies the solution takes
We are left with the problem of computing the frequencies.
We want to compute an array
belongs to a query of
Computing this array by updating every entry of
We can solve this problem using the prefix sum.
Let's consider an array
We need to only modify two entries of
This is done as follows:
Therefore the prefix sum of
This algorithm takes
The code clarifies the algorithm:
littleGirlMax(a[], q[])
n = a.length()
u[n] // compute U
for (l, r) in q
u[l]++
if r + 1 < n
u[r+1]--
f[n] // compute the prefixSum of U, aka F
pS = 0
for i = 0 to n
pS += u[i]
f[i] = pS
// sort the array and the frequencies in decreasing order
a.sortDecreasing()
f.sortDecreasing()
// return the maximized sum of the queries
res = 0
for i = 0 to n
res += a[i] * f[i]
return res
Given an array
Formally we need to find the number of pairs of indices
If
Then we compute an array
if A[n] == S/3
C[n] = 1
// iterate through A[] backwards to fill up C
suffixSum = A[n]
for i = n-1 to 1
suffixSum += A[i]
if suffixSum == S/3
C[i] = C[i+1] + 1
else
C[i] = C[i+1]
At this point we scan
Every time the prefix sum at position
This is because the part
Since the values in
Clarification:
Said Easy:
Given an integer array nums and an integer k, return true if nums has a good subarray or false otherwise.
A good subarray is a subarray where:
kFrom each element i in the array we compute every possible subarray starting in i and check that the sum of the elements of the subarray is a multiple of k, storing the maximum length so far.
The solution is based on a math property:
The algorithm then is as follows:
checkSubarraySum(array, k)
n = array.length()
prefixSumArray[] // prefix sum array
pS = 0
for i = 0 to n
pS += array[i]
prefixSumArray[i] = pS
// map: modulo -> index i st prefixSumArray[i] % k = modulo
HashMap modsToIndices
for (i, prefixSum) in prefixSumArray.enumerate()
modulo = prefixSum % k
// if modulo is 0 and not the first ok
if modulo == 0 && i != 0
return true
// first time we see this modulo
if modsToIndices.contains(modulo) == false
modsToIndices.insert(modulo, i)
else
// this modulo has been seen
previousIndex = modsToIndices.get(modulo);
// not the previous
if previousIndex < i - 1
return true
return false
The Fenwick Tree, aka Binary Indexed Tree, is a data structure that maintains the prefix sum of a dynamic array.
With this data structure we can update values in the original array and still answer prefix sum queries, both in logarithmic time.
Consider the following problem: we have an array
sum(i) returns the sum of elements in add(i,v) adds the value v to the entry To solve the above problem we can use two trivial solutions:
sum(i) is solved by scanning the array in add(i,v) costs sum(i) is solved in add(i,v) is solved by modifying all the entries from Both solutions are unsatisfactory in the tradeoff between the two operations.
The Fenwick Tree provide a better tradeoff for the problem as it efficiently handles these queries in
In fact the Fenwick Tree is an implicit data structure, which means it requires only
Let's introduce the Fenwick Tree with a running example.
Consider the following 1-indexed array:
and consider a simpler version of the problem: let's solve sum queries only for positions that are powers of
The solution of this simplified problem will be the first level of the fenwick tree:
We notice that:
With this solution we have that:
sum(i), simply access the node i, provided that i is a power of add(i,v), add v to all the nodes that covers ranges that include the position iadd(3,10), we need to add add(i,v), find the smallest power of i, this is the end of the range covered by the first node you have to update. Say that the corresponding node is indexed with j. We have to add v to the nodes We observe that sum takes constant time and add takes
This is promising: we have to extend the solution to positions that are not power of
Formally we are not supporting queries positions that falls within the ranges of two consecutive powers of sum(6) is not supported.
Fortunately enabling queries for such positions is a smaller instance of our problem, we can apply the same strategy by adding a new level to our tree.
The children of a node stores partial sums starting from the next element:
The emphasis is on starting. The node indexed with
Lemma: our two-level tree can handle sum(i) queries for positions that are either a power of
Proof:
i in the second levelExample: how to compute sum(5)
[1,5] is then divided in two subrangesWhich positions are still not supported?
The positions that are neither a power of
In our setting, we can't compute sum(7).
As before we just add a new level to our tree, so we can support positions that are the sum of three powers of
We are done, the above is the complete Fenwick Tree of the array
We can make some observations:
sum(i) - sum(i-1). This is why the Fenwick Tree is an implicit data structuresum(i) QueryThis query involves beginning at node
Thus sum(i) takes time proportional to the height of the tree, resulting in a time complexity of
Let's consider sum(7).
We start at node with index
This works because the ranges of these nodes (
Answering a sum query is straightforward if we are allowed to store the tree's structure.
However a significant part of the Fenwick tree's elegance lies in the fact that storing the tree is not actually necessary.
The point is that we can efficiently navigate from a node to its parent using a bit trick, which is why Fenwick Trees are also called Binary Indexed Trees.
Bit Trick: How to Compute the Parent of a Node
We want to compute the parent of a node and we want to do it quickly, without representing the structure of the tree.
Let's consider the binary representation of the indexes involved in the query sum(7):
Theorem: the binary representation of a node's parent can be obtained by removing the trailing one (i.e., the rightmost bit set to
addNow let's consider the add(i,v) operation.
We need to add the value v to each node whose range includes the position i.
Additionally the right siblings of the node i also include the position i in their ranges: siblings share the same starting positions and right siblings have increased sizes.
The right siblings of the parent of i, the right siblings of its grandparent and so on can also contain the position i.
It might seem like we have to modify a large number of nodes but in reality the number of nodes to be modified is at most
This is because each time we move from a node to its right sibling or to the right sibling of its parent, the size of the covered range at least doubles.
A range cannot double more than
Example: if we want to perform add(5,x) we just need to modify the nodes in red
Bit Trick to Compute the Sibling of a Node
Continuing with the example above, starting with i = 5, the next node to modify is its right sibling, the node
Their binary representation is
We see that if we isolate the trailing one in the binary representation of 0001) and add it to the representation of
The binary representation of a node and its sibling matches, expect for the position of the trailing one.
When we move from a node to its right sibling this trailing one shift one position to the left.
Adding this trailing one to a node accomplishes the required shift.
The time complexity is once again
We can use Fenwick Trees to perform range sums, that is the cumulative sums of any range sum(r) - sum(l).
We are given an array
If
The goal is to count the number of inversions of
We assume that the largest integer
This assumption is important because we are using a Fenwick Tree of size
If this assumption does not hold then we sort
If elements are equal then they have the same rank.
Main point: rank goes from
To solve the problem we use a Fenwick Tree FT on an array FT is used to keep track of elements that we have already processed.
We initialize a counter variable res and scan the array
When we process
counter += FT.range_sum(A[i]+1, n)FT.add(A[i], 1)Since both range_sum and add cost
Said Easy:
Let's see it in action in the first two iterations.
We scan the array using
When FT, the array
We process
counter += FT.range_sum(A[i]+1, n), which is zero as we have just startedFT.add(A[i], 1), which "means" Now we go to the next element,
We process
counter += FT.range_sum(A[j]+1, n)FT.range_sum(A[j]+1) counts the number of elements bigger than Consider an array
Consider two operations to support:
access(i): returns range_update(l,r,v): update the entries in v.You have
We use a Fenwick Tree to efficiently solve the problem:
FT of length access(i) is a wrapper of the query sum we have seen so far: range_update(l,r,v) exploit the operation add(i,v)add(l,v): add v to each node whose range include the position l in FTadd(r+1, -v): subtract v to each node whose range includes r in FTv in FT, this means that the prefix sums are coherent and the elements in [l,r] are increased by vClarification:
Better said: sum(i) in the current setting results in the access operation: sum(i) == access(i)
Example: Consider the empty FT represented as an array
range_update(1,2,2)[0,2,0,-2][0,2,2,0]access(2); we want the third element of the arraysum(2) is the prefix sum of the elements [0,1,2] of the FTsum(2) = Note: we use 1-indexing.
The range update of the previous problem is paired with the access operation.
Now we want to support the following operations:
range_update(l,r,v), same as beforesum(i), returns We notice that :
add(i,v) is a special case of range update:range_update(l,r,v) with r-l+1 call to add, but this would cost access(i) will be supported by performing sum(i) - sum(i-1)In our initial approach we follow a similar strategy to the one used in the "Update the Array" problem.
For a range_update(l,r,v) we modify the fenwick tree by adding v in position l and subtracting v in position r+1.
When querying sum(i) we multiply the result by i.
This approach is flawed:
FTrange_update(2,4,2)[0,2,2,2,0,0]FT is [0,2,0,0,-2,0] as a result of the range update querysum(3)sum(i) == access(i), and in fact sum(3) on FT gives us 2, hence sum(3) = 2 * 3 = 6, which is wrongFormally: consider range_update(l,r,v) on a brand new FT (all zeroes).
The results returned by our method are the following:
sum(i) is sum(i) is sum(i) is The correct result of a sum(i) after the range_update is:
sum(i) is sum(i) is v times the number of entries modified by the range updatesum(i) is v times the length of the range In words: our implementation reports the correct result for
Specifically, for
To fix those problems we employ another Fenwick Tree, FT2, which will keep track of these discrepancies.
When we perform a range_update(l,r,v) we:
ft1.add(l,v)ft1.add(r+1,-v)ft2.add(l, -v*(l-1))ft2.add(r+1, v*r)This revised approach ensures that the result of sum(i) can be expressed as
sum(i) in the first fenwick treeAnd we get
sum(i)
// a i b
ft1.sum(i) * i + ft2.sum(i)
The value of
A Segment Tree is a data structure that stores information about array intervals as a tree.
This allows answering range queries over an array efficiently, while still being flexible enough to allow quick modification of the array.
Range queries are more general than range sums: we can find the sum of consecutive array elements
Between answering such queries we can modify the elements by replacing one element of the array, or even change the elements of a whole subsegment, e.g., assign all elements in
We consider the simplest form of Segment Trees and we want to answer sum queries efficiently.
Formally: given an array
We can take a divide-and-conquer approach when it comes to array segments.
We compute and store the sum of elements of the whole array, i.e., the sum of the segment
Then we split the array into two halves
We can view this segment as forming a binary tree: the root is the whole array segment, and each vertex (except leaves) have exactly two children.
Example: consider the array
We can see that the segment tree only requires a linear number of vertices.
The first level contains a single node (the root), the second level will contains two nodes, the second will have four nodes and so on, until we reach
Thus, the number of vertices in the worst case can be estimated by the sum
Before constructing the segment tree we need to decide
Note that a vertex is a leaf if its corresponding segment covers only one element of the original array.
To build a segment tree we start at the bottom level, the leaves, and assign them their respective values. On the basis of these values we can compute the values of the previous levels, using the merge function, until we reach the root.
It convenient to describe this operation recursively in the other directions: from the root to the leaves.
In other terms: the construction is a post-visit, where the "visit" phase is the assignment of the value of the current node:
The time complexity of the construction is
Say that we receive two integers,
We can achieve this by traversing the tree and use the precomputed sums of the segments.
Assume that we are currently in a node that covers the segment
There are three possible cases:
In other terms: processing a sum query is done by a recursive function that calls itself once on either the left or the right child without changing the query boundaries, or calls itself twice, once for child, splitting the query in two subqueries.
The recursion ends whenever the boundaries of the current query segment coincides with the boundaries of the segment of the current vertex.
In that case the answer will be the precomputed value of the sum of this segment, which is stored in the tree.
Example: consider
We now have to show that we can compute sum queries in O(log(n)).
Theorem: for each level we only visit no more than four nodes, and since the height of the three is
Proof: we prove the theorem by induction:
A graphical intuition of the above proof:
Now we want to modify a specific element in the array, as in
This query is easier than the sum. Each level of a segment tree forms a partition of the array, therefore an element
Thus only
We can perform this query by employing a recursive function.
The function receive the current tree vertex and recursively calls on the child that contains
Example: consider
Segments Trees also allows applying modification queries to an entire segment of contiguous elements with the same time cost:
When we need to update an interval we will update a node and mark the child that needs to be updated, but actually update it later, only when needed.
To do so we can add to every node a field that marks if the current node has a pending update or not.
Then, when we perform another range update or a sum query, if nodes with a pending update are involved, we first perform the updates and then solve the query.
In other words: when there are many updates and updates are done on a range, we can postpone some updates (avoid recursive calls in update) and do those updates only when required.
Remember that a node in segment tree stores or represents result of a query for a range of indexes: if this node’s range lies within the update operation range, then all descendants of the node must also be updated.
Example:
Consider the node with value
If our update query is for the range
With lazy propagation we only update that node and postpone the updates on its descendants by storing this update information:
lazy[], which represents lazy nodes, all initialized to zeroes.lazy[i] = 0 indicates that there are no pending updates on the node i.lazy[i] != 0 than this amount needs to be added to the node i in the segment tree before making any query that involve the node.A persistent data structure is a data structure that remembers its previous state for each modification.
This allows to access any version of this data structure that interests us and execute a query on it.
We can efficiently create persistent segment trees.
In fact any change request in the segment tree leads to a change of only
If we store the segment tree using pointers then to perform the modification query we simply need to create new vertices instead of actually changing the available ones.
Vertices that are not affected by the modification can be reused, just use pointers to refer to them.
For each modification of the segment tree we will receive a new root vertex.
To quickly jump between versions we need to store the roots in an array, then to use a specific version of the segment tree we simply call the query on the right root vertex.
The following image gives an idea of how we can make a persistent segment tree:
We are given
There are no ends of some segments that coincide.
For each segment find the number of segments it contains.
In other words: for each segment
This solution involves a fenwick tree and the sweep line approach.
Let's build an array events where every entry is of the form
Then sort events by the first component of every entry,
At this point we build a fenwick tree with size events.
For each event ft.add(r_i, 1).
Now we scan the events again: when we process the event
To find the solution for the current segment (aka the number of segments contained in the current segment) we need to know the number of the segments that starts after the current one that also ends before the current one, before
This is computed with a query sum(r_i - 1) on the fenwick tree.
Then we perform ft.add(r_i, -1) to subtract
Why sum(r_i - 1) is the number of segments contained by
Because all the segments that starts before
In other words: the only segments that have
the current segment.
Thus sum(r_i - 1) is the number of segments that starts after
This is why segments that starts before the current one but overlaps with it are not counted.
The following snippets clarifies the algorithm:
nestedSegmentFT(segments[])
n = segments.length()
List result
List events
for (i, segment) in segments.enumerate()
events.push((segment.start, segment.end, i))
// sort by the first component of each element, s_i
events.sort()
tree = FenwickTree(2*n + 1)
for event in events
tree.add(event.end, 1)
for event in events
result.push((tree.sum(event.end - 1), event.index))
tree.add(event.end, -1)
// sort by the second element, the index, to
// restore the original ordering of segments
result.sort()
return result
Let's now solve the problem using a segment tree and sweep line.
Given an input array segments of ranges
We then create a segment tree based on an array of size
At this point we create an array axis that stores triples, where:
isStart which is true if the endpoint of this triple is an Now we sort axis by the first component, the segment endpoints.
Finally we sweep over the axis:
isStart == false)st.add(s_i, 1)Why it works?
When we find the end of the segment
Then we increase by st.add(s_i,1)) in the segment tree.
This works because we increase by one the start
We add 1 only when we find the end of a segment.
The range sum on
Given
add(i,v): rmq(l,r): We use a segment tree to solve the problem.
The range
The approach is identical to the one seen for computing the range sums.
We simply modify the construction of the segment tree so that every node stores the minimum element and its position.
Then we perform a query similar to the range sum that visit nodes and use the information of the visited nodes to build the answer
Given
add(i,v): rmq(l,r): We use a segment tree to solve the problem.
As in the previous problem (and as always with STs) we store the information on the nodes.
You build again the tree by saving the minimum and the number of occurrences from the ground up.
The minimum of a leaf (a segment of length
Going up we merge the info of the children. If an element is smaller than the other than the info stored in that node will equal to the info that stores the smaller element.
If the minimums stored in the two children are equal then we take the same element as the minimum and sum the number of occurrences.
As before we simply modify the construction method of the tree, and the query behaves as the range sum query.
Consider an array
We want to provide the following three operations:
add(i,v), same as beforerange_sum(l,r), same as beforesearch(s): report the position Prefix Sums are monotone (we have non-negative values), non-decreasing. In other words the prefix sums are sorted in increasing order.
We can binary search the answer.
We build a segment tree to efficiently answer range sum queries (which include prefix sums, as a prefix sum is a range sum with left endpoint equal to
The range of possible answers is
At this point we binary search the answer: we get to the middle element mid of the range of possible answers and perform a query range_sum(0, mid).
If the answer to that query is a value that is >= mid. Otherwise we recur on the right half of the array.
At the end we will return the smallest index mid such that
For each iteration of binary search we perform a range_sum to verify that the predicate
Binary search recur
Therefore a query search(s) costs
In the trivial solution we do not fully exploit the segment tree.
In fact we do not need to binary search the answer.
We want the smallest index i such that the sum of the elements in >=
The algorithm is presented with the following example:
In other words: we try to go left, if the range sum stored in left node is >=
If in the left child the sum is smaller than
Going right we just need to find the range sum range_sum(0, i) + range_sum(i+1, j) >= s.
Therefore we subtract to
Time Complexity:
It is clear that we resolve a search(s) query with just one inspection of the tree, and we discard one of the two subtrees in every recursion. Therefore the complexity is
Given a binary vector
We want to provide the following operations:
add(i,b), range_sum(l,r)select(i), report the position of the The select(i) operation is equal to the operation search(s) we have seen in the previous problem, therefore the approach to solve the problem is identical.
The key insight is to notice that if the
This problem is an harder variation of the previous one.
Given a binary vector
We want to provide the following operations:
add(i,b), range_sum(l,r), also called rank_1(l,r) for binary vectorshard_select(l,r,k), report the [l,r]We build upon the "Select" we have seen before, and we notice that actually hard_select(l,r,k) == select(k + range_sum(0, l-1)).
Consider an array
We want to provide
add(i,v)occs(l,r,x), reports the number of occurrences of x in the subarray As we have seen before we have to store information on nodes, and build upon that info to retrieve the info of the parent.
In this case we store, for every node, an hash-map that maps an element of the array with the number of occurrences of that element in the segment covered by the node.
When we build we will start, as always, from the leaves node which will have only the mapping element -> 1.
Going up we will "merge" the hash-map, updating the occurrences of elements that appear in both the map of the left and right child, and inserting the elements that appear only in one of the two child.
Once the tree is built (the building process will be slower than the one seen for range sums, as there is the merging of maps) a query occs(l,r,x) simply cost range_sum).
What is the space requirement?
todo
Every element can be at most in
Therefore the space requirement is
Consider an array
We want to provide the following operations:
add(i,v)successor(l,r,x), reports the successor of x in We again use a segment tree. We have to store meaningful information in every node of the tree so that we can use it to build the info of a parent node.
In this case for every node we need a fast way to retrieve the successor of an element x
We store a BST in every node of the segment tree.
The successor query on a BST requires
When we traverse the ST we combine the answers by taking the minimum.
The minimum of all the BST successor queries gives us the smallest element that is bigger than x, aka its successor.
The overall time for a successor(l,r,x) query is
We see at most
What is the space usage?
todo
Every BST takes linear space in the number of elements in the subtree. Every single element is at most in
Given an array of integers
We want to count the number of triplets
We consider any pair
Once we fixed
If
We need a way to efficiently compute the number of indices
The key lies in the fact that we can choose the pairs in the order we want.
We process pairs so that when a
In other words: when we choose a
The overall cost
Can we do better? An alternative to the previous solution is:
The above approach is still quadratic as we are scanning, for every fixed
However this approach is insightful. For every
Summary of the problem:
The index
We then need an efficient data structure to compute
Basically
The said data structure must be able to tell me, for every
In order to do this we remap the values in
This is done by sorting the array and replace every element with its rank in the sorted array. It is obvious that if a triple were to be counted before it will also be counted now.
The complexity is given by the sorting, thus
At this point all the elements are in
We can use a segment tree
TODO
At this point to compute sum(A[j]-1) to
Similarly we use a segment tree
To compute range_sum(A[j]+1, n-1), which is equal to the number of elements in
For every
Then we need to add the cost of updating the prefix and suffix every time we move
The Mo's algorithm is a technique for solving a wide variety of range query problems.
It becomes particularly useful for kind of queries where the use of segment trees or similar data structures are not feasible.
This happen when queries are non-associative: the result of query on a range cannot be derived by combining the answer of subqueries.
Mo's algorithm typically achieves a time complexity of
Let's show the Mo's Algorithm in action through the problem "Three of More"
We are given an array
Additionally we are given a set of three_or_more: the query three_or_more(l,r) aims to count the number of colors that occur at least three times in the subarray
The trivial solution of the problem is to use an additional array as a counter to keep track of occurrences of each color within the range and scan the queried subarray.
Whenever a color reaches
The catch here is that we have to reset the array of counters after each query.
It is clear that this solution has a time complexity of
The figure below illustrate an input that showcases the worst-case running time.
Say that we have
The total length of these ranges is
Let's improve the solution using the Mo's Algorithm.
Suppose we have just answered the query for the range
Instead of starting from scratch we can build upon the previous query by adding or removing the contributions of colors that are new in the query range but not in the previous one, or vice versa.
Specifically:
Mind that the time complexity of the algorithm is unchanged, it is still
The key insight here is that a query executes faster it its range significantly overlaps with the range of the previous query.
The previous figure becomes now a best case scenario: the first query takes
We see that the order of the queries have a great impact on the time complexity.
Even now we can reorganize the queries to go back to quadratic time.
However this consideration leads to a question: if we have a sufficient number of queries, can we rearrange them in a way that exploits the overlap between successive queries in order to gain an asymptotic advantage in the overall running time?
Mo's Algorithm answers positively to this question by providing a reordering of the queries such that the time complexity is reduced to
How to reorganize the queries.
We conceptually divides the array in
A query belongs to a bucket
In other words:
Initially we group the queries based on their corresponding buckets, and within each bucket we sort the queries in ascending order of their right endpoints.
The figure shows the bucketing approach and how the queries of one bucket are sorted
Let's analyze the complexity of the solution using this ordering.
We count the number of times we move the indexes
This is because adding and removing the contribution of a color takes constant time, and thus the time complexity is proportional to the overall number of moves of these two indices.
Let's consider a specific bucket.
As we process the queries in ascending order of their right endpoints, the index
On the other hand the index
Hence, for a bucket with
Summing up over all buckets the time complexity is
The following code is the implementation of three or more and its application using the Mo's Algorithm:
pub fn three_or_more(a: &[usize], queries: &[(usize, usize)]) -> Vec<usize> {
let max = a.iter().max().unwrap()
let mut counters: Vec<usize> = vec![0; max];
let mut answers = Vec::with_capacity(queries.len());
let mut old_l = 0; // l'
let mut old_r = 0; // r'
let mut answer = 0;
for &(l, r) in queries {
// macros that add or remove the contributions
// of colors of the current query from the previous one
let mut add = |i| {
counters[a[i]] += 1;
if counters[a[i]] == 3 {
answer += 1
}
};
let mut remove = |i| {
counters[a[i]] -= 1;
if counters[a[i]] == 2 {
answer -= 1
}
};
while old_l > l {
old_l -= 1;
add(old_l);
}
while old_l < l {
remove(old_l);
cur_l += 1;
}
while old_r <= r {
add(old_r);
old_r += 1;
}
while old_r > r + 1 {
old_r -= 1;
remove(old_r);
}
answers.push(answer);
}
answers
}
pub fn mos(a: &[usize], queries: &[(usize, usize)]) -> Vec<usize> {
let mut sorted_queries: Vec<_> = queries.iter().cloned().collect();
let mut permutation: Vec<usize> = (0..queries.len()).collect();
let sqrt_n = (a.len() as f64) as usize + 1;
// sort queries by bucket and get the permutation induced by sorting.
// the latter needed to permute the answers to the original ordering
sorted_queries.sort_by_key(|&(l, r)| (l / sqrt_n, r));
permutation.sort_by_key(|&i| (queries[i].0 / sqrt_n, queries[i].1));
let answers = three_or_more(a, &sorted_queries);
let mut permuted_answers = vec![0; answers.len()];
for (i, answer) in permutation.into_iter().zip(answers) {
permuted_answers[i] = answer;
}
permuted_answers
}
Final Considerations on Mo's Algorithm:
Mo’s algorithm is an offline approach, which means we cannot use it when we are constrained to a specific order of queries or when update operations are involved.
When implementing Mo’s algorithm, the most challenging aspect is implementing the functions that add and remove contributions from the previous query result.
There are query types for which these operations are not as straightforward as in previous problem and require the use of more advanced data structures than just an array of counters.
Consider an array
Let us consider its arbitrary subarray
For every positive integer
We call the power of the subarray the sum of products
The sum contains only finite number of non-zero summands as the number of different values in the array is indeed finite.
You should calculate the power of
We can use Mo's Algorithm and a little bit of attention in updating the answer after an add or a remove.
The solution is identical to the one seen in the problem "Three or More" with one difference: we are not interested anymore in the number of occurrences of
In other words:
let mut add = |i| {
// we found another occurrence of i, we remove the old "power"
sum -= counters[a[i]] * counters[a[i]] * a[i];
counters[a[i]] += 1;
// we update the power using the right number of occurreces of i
sum += counters[a[i]] * counters[a[i]] * a[i];
};
let mut remove = |i| {
sum -= counters[a[i]] * counters[a[i]] * a[i];
counters[a[i]] -= 1;
sum += counters[a[i]] * counters[a[i]] * a[i];
};
TODO
Given an array rmq(l,r) that returns the position of the minimum element in
In other words:
Static means that
A simple solution is to create a 2D array lookup[][] where an entry lookup[i][j] stores the minimum value in
Note: lookup[i][j] store the index of the minimum element in the range [i,j].
Once the table is built we can answer a query in
To process of building the table is the following:
preprocess(a[])
n = a.length()
lookup[n][n]
for i = 0 to n
// the minimum for the ranges [i,i] (of length 1) is 1
lookup[i][i] = 1
for i = 0 to n
for j = i+1 to n
if a[lookup[i][j-1]] < a[j]
lookup[i][j] = lookup[i][j-1]
else
lookup[i][j] = j
The time to build the table is
At this point any query rmq(l,r) is directly answered with a[lookup[l][r]] in constant time.
The idea is to precompute a minimum of all subarrays of size
As before we build a lookup table. Here lookup[i][j] contains (the index) of the minimum of the range starting from
For example, lookup[0][3] contains the minimum of the range [0,7] (starting from
How we fill up this table:
We fill it in a bottom-up manner using previously computed values.
For example to find a minimum of range [0,7] we can use a minimum of the following two:
[0,3][4,7]Based on the above example:
// eg: if a[lookup[0][2]] <= a[lookup[4][2]]
// lookup[0][3] = lookup[0][2]
if a[lookup[i][j-1]] <= a[lookup[i+2^(j-1)][j-1]]
lookup[i][j] = lookup[i][j-1]
// eg: if a[lookup[0][2]] > a[lookup[4][2]
// lookup[0][3] = lookup[4][2]
else
lookup[i][j] = lookup[i+2^(j-1)][j-1]
How we compute the Query:
For any arbitrary query [l,r] we need two ranges that are in powers of
The idea is to use the closest power of
One range starts with l and ends with l + closest-power-of-2.
The other range starts with r - closest-power-of-2 + 1 and ends with r.
For example, if the given range is [2,10] we compare the minimum of the two ranges [2,9] and [3,10].
Formally:
// for (2,10), j = floor(Log2(10-2+1)) = 3
j = floor(Log(r-l+1))
// if a[lookup[0][3]] <= a[lookup[3][3]] then rmq(2,10) = lookup[0][3]
if a[lookup[L][j]] <= a[lookup[r- 2^j +1][j]]
rmq(l, r) = lookup[l][j]
// if a[lookup[0][3]] > a[lookup[3][3]], then rmq(2,10) = lookup[3][3]
else
rmq(l, r) = lookup[r- 2^j +1][j]
Dynamic Programming, like divide-and-conquer, solves problems combining solutions of subproblems.
Divide-and-conquer algorithms partition the problems into disjoint subproblems, solve them, and then combine their solution to solve the original problem.
In contract, dynamic programming applies when subproblems overlap, that is when sub-problems share sub-sub-problems.
In this context a divide-and-conquer problem does more work than necessary, repeatedly solving the shared sub-sub-problems.
A DP algorithm solve each sub-sub-problem just once and saves its solution in a table, avoiding the work of recomputing the answer every time it solves each sub-sub-problem.
Let's consider a first easy example: Fibonacci's Numbers
Fibonacci's numbers are defined as
Our goal is to compute the
Let's consider the following trivial recursive algorithm:
fibonacci(n)
if n == 0
return 0
if n == 1
return 1
return fibonacci(n-1) + fibonacci(n-2)
In computing fibonacci(n-1) we will compute fibonacci(n-2) and fibonacci(n-3), and in computing fibonacci(n-2) we will compute fibonacci(n-3) and fibonacci(n-4), and so on.
There are lots of the same Fibonacci numbers that are computed every time from scratch.
To avoid the above waste of computations we use the top-down approach called Memoization.
Whenever we compute a Fibonacci number we store it in an array M.
Every time we need a Fibonacci number we check if it is already in the array. If the number is present we just reuse it, otherwise we compute it and store it.
This algorithm requires linear time and space.
memFibonacciDP(n)
if n == 0
return 0
if n == 1
return 1
if M[n] == -1
M[n] = fibonacci(n-1) + fibonacci(n-2)
return M[n]
In DP we also have a bottom-up approach, called Tabulation, which uses linear time and constant space.
This approach typically depends on some natural notion of "size" of a sub-problem, such that solving any particular sub-problem depends only on solving "smaller" sub-sub-problems.
Basically we solve the subproblems in ascending order by their size.
When solving a particular subproblem we are sure that we have already solved all the smaller sub-sub-problems its solution depends upon.
tabFibonacci(n)
F[n]
F[0] = 0
F[1] = 1
for i = 2 to n
F[i] = F[i-1] + F[i-2]
return F[n-1]
Memoization vs Tabulation
Tabulation and Memoization are two common techniques used in DP to optimize the solution of problems by avoiding redundant computations and storing intermediate results.
To summarize:
The fastest way is to exploit matrix multiplication:
How can we compute efficiently
Let's consider
Then you keep on decomposing by half until you reach an immediate result, which you then propagate backwards.
Since we can decompose by half
You are given an board where the cells are labelled from
starting from the bottom left of the board (i.e. board[n-1][0]) and alternating direction each row, e.g:
The objective is to start from 1 and reach 100 using a dice.
You move following the order of numbers: starting from
The problem is that in the board here are both snakes and ladders.
Snakes and Ladders impose a behavior for the player:
In other words: ladders are good, snakes are bad.
Given a board, what is the minimum number of moves to reach 100 from 1?
We are kinda asked the shortest "sequence" of cells we traverse to reach the destination.
Turns out we can actually transform the game into a graph and then apply the shortest path in a DAG:
In the above scheme we see in blue the edges that represent ladders, in green the edges that represent snakes.
In red we see the case where from
The same would be for snakes.
Once you have inserted "the red edges" you can actually forget about snakes and ladders.
Since the source is
Mind that the computation of the shortest path on a unitary costs DAG translates to a BFS: as soon the destination enters the frontier you have found the shortest path.
Since we use a BFS we have that the cost is
Since
How many ways are there to make a
Example:
The subproblems in this case are clear: just consider shorter strings.
Consider an array M[n] where
It is obvious that:
M[0] = 1, as with M[1] = 2, as with M[2] = 3 (M[3] = 5Formally:
Its the Fibonacci's sequence: we can compute it in
Consider a
How many tessellation are there for the board?
It is Fibonacci again, only "shifted by one"
Serling Enterprises buys long steel rods and cuts them into shorter rods, which then sells. Each cut is free.
What is the best way to cut up rods?
Consider a rod of length
The goal is to determine the maximum revenue
We fill an array
Every entry
Assuming that we have already solved all the subproblems of size
Let's list all the possibilities:
The value of
In a tabulation fashion we compute the max profit for all rods of length up to
The following snippet clarifies the algorithm:
rodCutting(rod[])
n = rod.length()
R[n+1] // initialized with all zeroes
for i = 1 to n // length of the rod
q = 0 // max profit for the "current" rod
// best way to cut?
for j = 0 to i
// q is the max between q and price of the rod of length i
// plus the maximum profit obtainable by the the rod of
// length i - j
q = Math.max(q, rod[i].p + R[i-j])
R[j] = q
return R[n]
We are given a matrix
The goal is to find the minimum cost path to move from the top-left corner to the bottom-right corner.
Mind that you only have two possible moves:
The idea is to fill a
Said Easy:
We can think of
You always pay the cost of being in the cell you are when computing
Basically the first row and column of
Example: to reach
Then, to reach an "internal" cell of
The time complexity is
Given two strings, S1 and S2, of length
Observation: subsequence
The subproblems here ask to compute the longest common subsequence (LCS) of prefixes of two sequences, S1 and S2.
Subproblem: Given two prefixes S1[1..i] and S2[1..j] our goal is to compute the LCS of those two prefixes.
Assume that we already know the solutions to the following smaller problems:
LCS(S1[1..i-1], S2[1..j-1])LCS(S1[1..i], S2[1..j-1]) LCS(S1[1..i-1], S2[1..j]) Then we have that:
S1[i] == S2[j] we can extend the LCS of S1[1..i-1] and S2[1..j-1] by adding one character, c = S1[i] = S2[j]Summarizing:
Therefore we use a dp to store the intermediate results.
Formally dp[i][j] = LCS(S1[1,i], S2[1,j]).
We set the first row and column to 0 (as they represent the LCS with prefix length 0) and iterate, using two nested loop, to check if S1[i] == S2[j].
In such cases we increase by one the previous LCS (dp[i-1][j-1]), otherwise we pick the max between the LCS of S1 without the current character and S2 without the current character.
We return dp[n][m], which is the LCS of S1[1..n] and S2[1..m], aka S1 and S2.
LCS(S1, S2)
n = S1.length() + 1
m = S2.length() + 1
// first row and colum are initialized to zeroes
// as the LCS of two strings using 0 chars of one is 0
dp[n][m]
for i = 0 to n
dp[i][0] = 0
for j = 0 to m
dp[0][j] = 0
for i = 1 to n
for j = 1 to m
if S1[i] == S2[j]
dp[i][j] = dp[i-1][j-1] + 1
else
dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j])
return dp[n][m]
Consider an array
Each element
This means that if
Find the minimum number of jumps to reach the end of the array starting from the beginning of the array. Return
We use an array jumps to store intermediate results.
Formally jumps[i] is the minimum number of jumps needed to reach the position
The solution is in the following snippet:
minJumps(A[])
n = A.length
jumps[n]
// before starting the only reachable position
// is the starting position, which requires 0 jumps.
jumps[0] = 0
for i = 1 to n
jumps[i] = MAX
for i = 1 to n // subproblems: jumps up to n, the end of the array
for j = 0 to i // compute the solution for each subproblem
if j + A[j] >= i && jumps[j] != MAX
jumps[i] = Math.min(jumps[i], jumps[j] + 1)
break
return jumps[n-1]
The key is the if guard inside the two loops:
j + A[j] >= i: we want to reach the position i and we are currently in the position j. If j + A[j] >= i it means that from j, plus the length of the jump we can make from j (A[j]), we can actually reach ijumps[j] != MAX: we can actually reach the position j from the start of the arrayThen the minimum number of jumps required to reach i is the minimum between the current minimum number of jumps to reach i (jumps[i]) and the jumps required to reach j plus the one jump to reach i (jumps[j] + 1).
We are given
We want to put a subset of these items in a knapsack of capacity
It is called 0/1 because an item is either selected or not.
We have three solutions to this problem:
1) Solution with Weight Dynamic Programming
We fill a
We then have:
The last entry of the matrix
2) Solution with Profit Dynamic Programming
The idea is similar to the previous one.
We use a matrix a
Formally
We then have that
Consider
The pair are "vertical", as in
The value of the coin
The objective is to select
Every coin is a node in a graph.
Longest Path on a DAG: the complexity is proportional to the number of edges and we have
This problem can be reduced to a specific instance of the Knapsack Problem.
In this case we have that the capacity is
The difference from the classical knapsack is that we also have to consider the constraint on the coin pairs.
The idea is the following:
We have to fil a matrix that is
Given a set
The problem is a well-known NP-Hard problem, which admits a pseudo-polynomial time algorithm.
pippo
The solution is almost identical to the one of the 0/1 Knapsack Problem.
We construct a boolean
Formally true if and only if there exists a subset of the first
The entries of the first row, false as with
Similarly, the entries of the first column, true as with the first
Then we have that:
To sum up:
Given a set
The solution is almost identical to problems we have already seen.
The idea is to fill a table W of n+1 rows and V+1 columns, where W[i][j] is true if using a subset of i elements we can make a sum equal to j.
We then have:
Given an array of integers
Mind that in general the LIS is not unique.
Observation: as before, subsequence
Given LIS(i) be the longest increasing subsequence of the prefix
Then we have that:
We use an array lis of size n+1, where lis[i] is the LIS of the prefix
The solution is directly given as code:
LIS(S)
n = S.length()
n++
lis[n]
// the LIS of the null prefix is 0
lis[0] = 0
for i = 1 to n
lis[i] = 1
// i is the current element
for i = 1 to n
// j is used to to compute the LIS of the prfix up to i
for j = 0 to i
if S[i] > S[j] && lis[i] < lis[j] + 1
lis[i] = lis[j] + 1
return lis.max()
S[i] is greater than the element S[j] (meaning that the element at position i could be the next element of the sequence that ends at position j)S[i] is shorter than the sequence that ends in j (lis[j]) plus 1, the "maybe added" element `S[i]lis[i] = lis[j] + 1todo
The main idea of this approach is to simulate the process of finding a subsequence by maintaining a list of "buckets", where each bucket represents a valid subsequence.
We start with an empty list ans and iterate through the input array S.
For each e in S:
e is greater than the last element of the last bucket, aka the largest element in the current subsequence, we append e to the end of ans.ans to find the position of smallest element that is > e in ans. This step help us to maintain the property of increasing elements in the buckets (ans). Once we have found such position we replace the element in that position with e: this keeps ans sorted and ensures that we have the potential for a longer subsequence in the future.Consider the following implementation:
LIS(S)
n = S.length()
List ans
ans.add(S[0])
for i = 1 to n
if S[i] > ans.last()
ans.add(S[i])
else
// smallestBS return the index of the
// smallest element that is >= S[i] in ans
low = smallestBS(ans, S[i])
ans[low] = S[i]
return ans.length()
In other words:
ans is the length of the current LISS[i] in ans[low]low is the index of the smallest element that is >= e in ans: we can always substitute it with a smaller element e without affecting the LISe: when we substitute we insert in a place that is still part of the current LIS, but if a new LIS would start entirely from e every element would be also substituted!It is often useful to reduce a problem to a (single source) path computation on a suitable DAG (directed acyclic graph).
Let's consider again the Longest Increasing Subsequence problem: we build a suitable DAG
Let's build
We use
Every vertex has an edge to
By construction exists a one-to-one correspondence between increasing subsequences in
Any longest path on
Our
For any
In other words: any sequence of length
Let's consider the sequence
Let be LIS[] and LDS[] the dynamic programming table for the longest increasing and decreasing subsequence of
Formally, LIS[i] and LDS[i] are the longest increasing and longest decreasing subsequences that end in S[i], respectively.
Consider for each position i the pair <LIS[i], LDS[i]>.
Claim: there are no equal pairs.
Proof:
Consider two positions i and j, with i < j.
Since the elements in S are distinct we have only two cases:
S[i] < S[j], and therefore LIS[i] + 1 <= LIS[j]S[i] > S[j], and therefore LDS[i] >= LDS[j]+1Let's assume for absurd that the LIS is of length
In other words we assume that LIS
In this scenario how many pairs we can make? Since LIS is at most
Now, since LIS and LDS have length
For the pigeon hole principle this means that some pair must be repeated, but we know that there cannot be repeated pairs.
Therefore the length of the LIS and/or LDS have to greater, at least
We have
Each coin is given in the array
The goal is to find out in how many ways we can change the amount
Example:
The solution is inspired to the one of "0/1 Knapsack" and even more so to "Partial Equal Subset Sum".
We build a
The code clarifies the solution:
coinChange(coins[], k)
n = coins.length()
W[n+1][k+1]
// the number of ways to change 0 with no coin
W[0][0] = 0
// with any subset of coin you can change 0, just dont use coins
for i = 1 to n+1
W[i][0] = 1
for i = 1 to n+1
for j = 1 to k+1
if coins[i-1] > j
// the current coin is alone bigger than k,
// we cannot use it to change k
W[i][j] = W[i-1][j]
else
// the number of ways to change j is the sum between
// 1) #ways without using the coin i
// 2) #ways using the coin i to make (j - coins[i])
W[i][j] =
W[i-1][j] +
W[i][j-coins[i]]
return W[n][k]
Given a sequence
A bitonic subsequence is a subsequence that first increases and then decreases.
This problem is a variation of the Longest Increasing Subsequence.
We construct two arrays lis[] and lds[] using the solution of LIS:
lis[i] stores the length of the longest increasing subsequence ending with S[i]lds[i] stores the length of the longest decreasing subsequence starting from S[i]The solution is given by finding the maximum value lis[i] + lds[i] - 1, where i is from 0 to n-1.
Given a tree n nodes find one of its largest independent sets.
An independent set is a set of nodes
Example: the nodes in red form a largest independent set in their tree:
For every node
Let LIST(u) be the size of the independent set of the subtree rooted in
We then define:
We can now define the following recurrence:
Then to algorithm is given by the following snippet
solution(tree)
n = tree.size() // num nodes
lis[n] // initialized with all -1
res = list(root, lis)
list(u, lis)
if u == null
return 0
if lis[u] != -1
return lis[u]
// we use u and maybe his grandchildren
uUsed = 1
if u.left != null
uUsed += Max(list(u.left.left, lis), list(u.left.right, lis))
if u.right != null
uUsed += Max(list(u.rigth.left, lis), list(u.right,right, lis))
// we dont use u, maybe his children
uNotUsed = 0
uNotUsed += list(u.left, lis) + list(u.right, lis)
// is better to use u and his grandchildren or only his children
res = Max(uUsed, uNotUsed)
lis[u] = res
return res
A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage.
In many problems a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time.
Most problems for which greedy algorithms yields good solutions (aka good approximation of the globally optimal solution) have two properties:
Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit.
Consider a sequence of
Every coin has an associated value.
We have two players, Alice (the 1st player) and Bob (the 2nd player).
The game start with Alice that can take a coin, either at start or at the end of the sequence. Then is the turn of Bob, and he can take either the first of last coin of the "updated" sequence.
The game goes on until all there are coins.
The game is won by the player that collected the coins with largest value. In other words the richest player wins.
Is there a strategy for Alice that guarantees that the value she collect is at least the same as the amount of Bob?
In other words: is there a strategy that guarantees Money Alice >= Money Bob?
We can label a coin with E if the coin is in an even position in the sequence, and we can label coins in odd positions with O.
Alice starts first: she can force Bob to take only odd or even coins!
Then the solution is to:
This greedy strategy is not the most obvious strategy but it is correct.
When attacking problems with a greedy strategy you have to be extra careful, as intuitive strategies might be negated by tricky counterexamples.
You are given
Select the maximum number of activities that can be performed by a single person, assuming that a person can only work on a single activity at the time, aka no overlaps are allowed.
The greedy solution is achieved by sorting the activities in ascending order **by their finish. This takes care of all the tricky overlaps.
activitySel(activities[])
n = activities.length()
// sort by ascending order of activities[i].end
activities.sort()
res = 1
last = activities[0]
for i = 1 to n
// if the current activity starts at least when the
// the last activity ends than it can be done.
// we are sure that the current activity will end after the
// end of the last activity as they are sorted by ends
if activities[i].start >= last.end
res++
last = actitvities[i]
return res
Why it Works?
Lemma: Exists at least an optimal solution which includes the activity with the smallest ending time, which is the first activity selected by our strategy.
Proof:
You are given an array of jobs where every job has an id, a deadline and a profit that can be achieved if the job is completed before its deadline.
It is also given that every job takes a single unit of time, so the minimum possible deadline for any job is
We start at time
Maximize the total profit, considering that only one job can be done at a time.
If we relax the problem so that a job must be executed exactly as its deadline is very easy to find an optimal solution. For jobs with same deadline just pick the most profitable one. Start selecting "backwards": pick the most profitable job with the latest deadline and schedule it for that time, then move back to the previous time slot and do the same.
What about the general problem? We can schedule a job to be executed any time before its deadline.
The approach has some similarity with the previous one. We still proceed backwards and put the most profitable job with latest deadline to be executed exactly on the time slot of its deadline.
But now we must also consider the case where there is another job with the same deadline. Before this job would be discarded but now it might survive, and more than that it: might be crucial to achieve the optimal solution.
We put that job to the previous time slot, with jobs that have as deadline that time slot, and select the job with highest profit.
The discarded jobs go backwards again, and so on.
Said Easy:
Put the most profitable job with latest deadline to be executed exactly on the time slot of its deadline.
For each time slot we might have many jobs with that deadline: we select the most profitable one.
The jobs that are not selected move backward, in the group of jobs that might be scheduled for the "previous" time slot, and repeat.
How it is Implemented?
We process time slots: for each time slot we have the jobs that have that time slot as deadline.
Then we use a Max-Heap to store the jobs that might be scheduled.
The max-heap is used to efficiently insert and retrieve jobs with maximum profit.
Going backwards from the last time slot: we insert all the jobs that might be scheduled there in the max-heap and then ask retrieve the maximum. That is the scheduled job for that time slot.
We then move backward to the previous time slot. Insert the jobs that might be done there in the max-heap and retrieve once again the max.
And so on.
The overall total complexity is
Consider
We want to put these items in a knapsack of capacity
In this version of the problem we can break the items for maximizing the total value.
The greedy approach is to calculate the ratio profit/weight for each item and then sort them on the basis of this ratio.
Consider that:
This will always give the maximum profit because in each step it adds an element such that this is the maximum possible profit for that much weight.
Consider
For each box
You can choose 1) any subset of boxes and 2) arrange them in any order you like.
Find the maximum number of boxes that can be used to form a tower, where for each box
To solve the problem we divide it in two tasks:
Then in the final solution you use the answer of 2) and then 1).
Step 1)
Assume we know an optimal ordering of boxes and let's find the best selection.
We use a
In the first row of the matrix,
Similarly, the first column of the matrix
When a cell
Then we have
The solution is then stored in the last row
We traverse the last row right to left (as we want the heighest possible tower) and stop at the first entry that is not zero.
The corresponding column index is the answer to the problem.
Filling this matrix requires
Step 2)
The above method works because we assumed the optimal ordering.
The optimal ordering guarantee that the box that we consider now, if usable, can be used as a base of the tower in an optimal solution.
When we add a box we always add it as a base.
Consider two boxes
In the ordering,
This is correct because
Lower in the tower means later in the ordering.
Remember: the optimal ordering guarantee that the currently considered box can be used as a base of the tower in an optimal solution (if it can be used).
Then we can rewrite
Bitor has
Each monster
Mind that Bitor can have more exceed
Find an ordering of monsters such that Bitor can defeat them all. Return
Observation: if Bitor reaches
The greedy choice is based on the following classification of monsters:
We sort the good monsters by increasing damage and the bad monsters by decreasing health bonus.
In words:
As Bitor face good monsters he will increase his health, as a good monsters gives more than he take.
This means that when Bitor will have defeated all the good monsters he will have maximum health.
Now Bitor will fight bad monsters, starting with monsters that restore the most possible health. After each fight he will have the most health possible in that situation, which will be used to fight the next monster.
If he can defeat all the bad monsters then Bitor is victorious.
The idea is given by the graph:
There is one meeting room in a firm.
There are
Find the maximum number of meetings that can be accommodated in the meeting room, knowing that only one meeting can be held in the meeting room at a particular time.
The solution is very similar to the one seen in "Activity Selection":
>= the ending time of the last meeting then we can have the meetingWilbur the pig is tinkering with arrays again.
He has the array
At one step he can choose any index
His goal is to end up with the array
Of course Wilbur wants to achieve this goal in the minimum number of steps and asks you to compute this value.
Example:
= [0,0,0,0,0][1,2,3,4,5], the target array +1 operation, one for every element ii = 0: +1 a = [1,1,1,1,1]i = 1: +1 a = [1,2,2,2,2]The solution is based upon the observation that the minimum number of operations is equal to the sum of differences (in absolute value) between consecutive elements of the target array.
Given the array
wilburAndArray(a[], b[])
n = a.length()
result = Math.abs(b[0])
for i = 1 to n
result += Math.abs(b[i] - b[i-1])
return result
Little Susie listens to fairy tales before bed every day. Today's fairy tale was about wood cutters and the little girl immediately started imagining the choppers cutting wood.
She imagined the situation that is described below.
There are
Each tree has its height
Woodcutters can cut a tree and fell it to the left or to the right.
After that it occupies one of the segments
The tree trait that is not cut down occupies a single point with coordinate
Woodcutters can fell a tree if the segment to be occupied by the fallen tree does not contain any occupied point.
The woodcutters want to process as many trees as possible.
What is the maximum number of trees to fell?
We use a greedy approach to solve the problem.
The code makes it even more clear:
woodcutters(trees)
n = trees.length()
// always cut at least the first and last trees
cutted = 2
for i = 1 to n-1
// left fall: the previous tree is placed before where the
// current trees fall when "left-cutted"
if trees[i-1].x < trees[i].x - trees[i].h
cutted++
continue
// cant fall to the left, lets try to the right
// if the current tree fall in a place that is smaller
// than the next tree place, then we cut
if trees[i].x trees[i].h < trees[i+1].x
cutted++
// update the position of the current tree
trees[i].x = trees[i].x + trees[i].h
continue
return result
}
A number is said to be magic if it is formed by a concatenation of
For example:
Determine if a given number is magic.
The approach is called greedy parsing. The idea is to find the longest match.
This is based on the Lempel-Ziv compression.
Always selecting the longest match is optimal, in Lempel-Ziv it can be proved that the greedy approach has the smallest number of phrases.
Therefore the optimal way to check if a number is magic is to parse it greedily, that is to "decompose" it by exploiting the longest possible matches:
Example:
To check that
The longest matches going through the number are:
For the case of
todo
Why the Lempel-Ziv (greedy parsing) is optimal (lowest number of matches)?
todo
Given a string S of length
Example:
S = a b a b b aLMS = b b b aWhy? If you select any other subsequence s than s is lexicographically smaller than LMS.
The lexicographically largest character will be the first character in our answer.
We scan the sequence S right to left, we keep track of the largest symbol we have seen so far and we select any letter which is at least as large. Any time we select we update the largest symbol seen so far if needed.
You have a queue of people waiting for something.
The person
The queue is destroyed (the persons in the queue are randomly shuffled).
The objective is to rebuild the queue.
Sort the people in a non-decreasing order using
If every person in a position
Given a graph
BFS computes the distance from
Another effect of the BFS is to produce a breadth-first tree rooted in
The tree contains all the nodes reachable from
For any vertex
Breadth-First search expands the frontier between discovered and undiscovered vertices uniformly across the breadth of the frontier.
You can think of it as discovering vertices in waves emanating from the source vertex.
Remember: a queue is a FIFO data structure:
The idea is the following:
bfs(G, s)
for v in G.nodes()
if v != s
v.color = "white" // node never "seen" (reached) before
v.distance = Math.MAX // maximum distance, unreachable
v.predecessor = null // no predecessor in the BF-tree
s.color = "gray" // a vertex seen for the first time becomes gray
s.distance = 0 // the distance from s to s is zero
s.predecessor = null // s has no predecessor
Queue frontier
// add s as the last element of the frontier
frontier.add(s)
while !frontier.isEmpty()
// pop element from the head of the queue
u = frontier.pop()
for v in u.neighbors() // consider all the neighbors of u
if v.color == "white" // if v was unreachable now is reachable
v.color = "gray"
v.distance = u.distance + 1
v.predecessor = u
frontier.push(v) // add v to the frontier
u.color = "black" // explored all neighbors: the node is black
Observation:
What if there is a cycle?
Time Complexity:
This cost arises from the need to visit each vertex once and traverse each edge once during the BFS traversal.
As its name implies, DFS searches "deeper" in the graph whenever is possible.
DFS also timestamps each vertex:
v.d records when v is first discovered (and "greyed")v.f records when the search finishes examining v's neighbors ("blackened")time // time is a global variable
dfs(G)
for u in G.nodes()
u.color = "white"
u.predecessor = null
time = 0 // time is initialized
for u in G.nodes()
if u.color = "white"
dfsVisit(G, u)
dfsVisit(G, u)
time++
u.d = time // time at which u has been discovered (u starting time)
u.color = "gray"
for v in u.neighbors()
if v.color = "white"
v.predecessor = u
dfsVisit(G, v)
time++
u.f = time // u's finishing time, u.f is in [1, 2*|V|]
u.color = "black"
Observation: DFS uses a stack instead of a queue to explore the nodes.
In the above implementation the stack is the activation records stack since the implementation is recursive.
Unlike BFS, whose predecessor subgraph forms a tree, depth-first search produce a predecessor graph that might contains several trees:
Therefore we define the predecessor subgraph of a depth-first search slightly differently from that of a BFS: it always includes all vertices, and it accounts for multiple sources.
Specifically for a depth-first search the predecessor subgraph is
The edges in
Note: DFS builds a DFS-tree when applied to a single connected component of an undirected graph or to the entire graph if it's connected.
However, in the case of a graph with multiple connected components, DFS produces a forest of DFS trees, often referred to as a DFS forest.
A strongly connected component of a graph
In other words: for every pair of vertices
During the execution of the DFS, different type of edges can be encountered.
Let's break down each type of edge:
Parenthesis Theorem:
Descendants in a depth-first-search tree have an interesting property.
If
In any DFS traversal of a graph
[u.d, u.f] and [v.d, v.f] are entirely disjoint and neither u nor v is a descendant of the other in the depth-first forest[u.d, u.f] is contained within the interval [v.d, v.f], and u is a descendant of v in a depth-first tree[u.v, v.f] is contained within the interval [u.d, u.f], and v is a descendant of u in a depth-first treeWhite-Path Theorem
A vertex v is a descendant of u if and only if there is a path from v to u with only white vertices at time u.d
Time Complexity:
Typically
This is because, in each recursive call, the algorithm explores all the edges incident to the current vertex, leading to a total of
Consider a graph
How can we check weather
We can simply run a DFS: if there exists a back edge than
Practically, when we are visiting the neighbors of a node
An application of DFS is the decomposition of a directed graph into its strongly connected components.
The solution use the transpose of
Observation: by construction
The algorithm is the following:
Given a direct or undirect graph
Said differently: given a graph with weighted edges (where each edge has a non-negative weight) the goal is to find the shortest path from a specified vertex (the source) to all other vertices in the graph.
From the CCLR:
Given a graph
Then we introduce:
This problem has an optimal substructure.
Lemma: given a weighted directed graph
There are two things to consider when solving this problem:
Dijkstra's Algorithm is a method for finding the shortest path from a single source vertex to all other vertices
It works for both directed and undirected graphs with non-negative edge weights.
The algorithm maintains a set of vertices whose shortest distance from the source is known, and continually expands this set by considering vertices with the minimum distance from the source.
The algorithm behaves as follows:
The algorithm is implemented in the following snippet:
dijkstra(G, s)
PriorityQueue q // a min priority queue
s.d = 0
for v in G.nodes()
if v != s
v.d = Math.MAX
q.add(v)
while !q.isEmpty()
// u is the vertex in Q with minimum distance from s
u = q.pop()
for v in u.neighbors()
weight = G.getWeight(u,v)
v.d = min(v.d, u,d + weight)
distances[n]
for i = 0 to n
distances[i] = graph.node(i).d
return distances
Time Complexity:
The time complexity of Dijkstra's algorithm depends on the data structures used to implement it.
Using a priority queue based on a binary heap, the time complexity is typically
Remember the complexity of a binary heap
Breakdown of the complexity
The Bellman-Ford algorithm is used to find the shortest paths from a single source vertex to all other vertices in a weighted graph, even in the presence of negative weight edges, as long as there are no negative weight cycles reachable from the source vertex.
Consider the following implementation: it takes in a graph, represented as lists of vertices (represented as integers
BF(G, s)
distances[n]
predecessors[n]
// step 1) initialization
for v in G.vertices
distances[v] = inf
predecessors[v] = null
distances[s] = 0
// step 2) relaxation
for v in G.nodes()
for (u,v) in G.edges()
w = G.getEdgeWeight((u,v))
if distances[u] + w < distances[v]
distances[v] = distances[u] + w
predecessors[v] = u
// step 3) check for negative cycles
for (u,v) in G.edges()
w = G.getEdgeWeight((u,v))
if distances[v] > distances[u] + w
return NegativeCycle
return distances, predecessors
The Bellman-Ford algorithm has a time complexity of
In the worst-case scenario, the algorithm needs to iterate through all edges for each vertex, resulting in this time complexity.
Consider the following toy Problem:
In a room, there are
A group of friends is a group of friends where any two pairs of persons are friends.
Given a list of persons that are directly friends find the number of groups of friends and the number of persons for each group.
Let's see an example: consider
Using the "transitive property of friendship" we will have only two group of friends:
This problem can be solved using a BFS (in
A Disjoint-Sets data structure is a structure that efficiently maintains a collection
Two sets are disjoint if their intersection is null.
In such a data structure every set contains a representative, which is a particular member of the set.
Consider the example above:
How can we check if two persons are in the same group?
This is where the representatives come in.
If a person
Lets define some operations:
create-set(x): create a new set with only the element xmerge-sets(x,y): merges the set that contains x with the set that contains yfind-set(x): returns the representative (or a pointer to it) of the set that contains xread(N) // N is the number of persons
for x = 1 to N
create-set(x)
for (x,y) in friends
if find-set(x) != find-set(y)
merge-sets(x,y)
Since sets are disjoint every time merge-sets(x,y) is called it will destroy two sets and create a new one.
If there are merge-sets(x,y) there will remain only one set. Thus the number of merge-sets(x,y) calls is create-sets(x)
We will analyze the running time of the disjoint-set data structure in terms of create-set(x) is called, and create-set(x), merge-sets(x, y) and find-set(x) are called.
One way to implement disjoint set data structures is to represent each set by a linked list. Each element will be in a linked list and will contain a pointer to the next element in the set, paired with another pointer to the representative of the set.
Example: the blue arrows are the pointers to the representative and the black ones are the pointers to the next element in the set
Using this implementation results in a complexity of create-set(x) and find-set(x).
The first will simply create a new linked list whose only element x and the second just returns the pointer to the representative of the set that contains x.
Let's now see how to implement the merge-sets(x,y).
The easy way is to append x's list onto the end of y's list.
The representative of the newly created set is the representative of the original set that contained y. After merging we must update the pointer of the representative of each element that was in x's list, which takes linear time in terms of x's list length.
It is easy to prove that in the worst case the complexity of the algorithm will be merge-sets(x,y).
With this implementation the complexity will average
The Weighted Union Heuristic
Let's see how a heuristic will make the algorithm more efficient.
Let's say that the representative of a set contains information about how many objects (elements) are in that set as well. The optimization is to always append the smaller list into the longer one and, in case of ties, append arbitrarily.
Basically the merge-sets will modify the representative of small set.
Say that we have a small set X. The set X could be involved in
Since changing the representative costs
This will bring the complexity of the algorithm to
So far we reached an algorithm that solve the problem in
Space wise the cost is
The BFS solves the problem in
We have optimized space, but not time.
The next step is to see what we can do for a faster implementation of disjoint set data structures.
Let's represent sets by rooted trees, with each node containing one element and each tree representing one set. Each element will point only to its parent and the root of each tree is the representative of that set (and its own parent).
Let's see how the trees will look in a step-by-step execution of the previous example:
Step 1: Nobody is anybody friend
We have
Step 2: merge-sets(1,2)
We now have
Step 3: merge-sets(5,4)
Step 4: merge-sets(5,1)
For now this implementation is not faster than the algorithm that uses linked lists.
Two Heuristics:
We now see how, using two heuristics, we will achieve the asymptotically fastest disjoint set data structure known so far, which is almost linear in terms of the number of operations made.
These two heuristics are called "union by rank" and "path compression".
The idea of union by rank is to make the root of the tree with fewer nodes point to the root of the tree with more nodes. For each node we maintain a rank that approximates the logarithm of the size of the subtree rooted in that node, and it is also an upper-bound of the height of the node.
When merge-sets(x,y) is called the root with smaller rank is made to point to the root with larger rank.
The idea in "path compression", used for find-set(x) operations, is to make each node on the find path point directly to the root. This will not change any ranks.
To implement a disjoint set forest with these heuristic we must keep track of ranks.
With each node x we keep the integer value rank[x], which is >= the number of edges in the longest path between x and a sub-leaf. todo: why?
When create-set(x) is called the initial rank is zero (rank[x] = 0).
When a merge-sets(x,y) is called the root with higher rank will become the parent of the root of lower rank (or in case of a tie we randomly chose one and increment its rank).
We then have that the operations are defined as follows:
P[N] // parents array, N number of elements
// P[x] is the parent of x
create-set(x)
P[x] = x
rank[x] = x
merge-sets(x,y)
PX = find-set(x)
PY = find-set(y)
if rank[PX] > rank[PY]
P[PY] = PX
else
P[PX] = PY
if rank[PX] == rank[PY]
rank[PY]++
find-set(x)
if x != P[x]
P[x] = find-set(P[x])
return P[x]
Let's see why the above implementation is faster than the previous ones.
If we only use the "union by rank" heuristic then we will get the same running time we achieved with the "weighted union" heuristic when we used lists.
When we use both "union by rank" and "path compression", the worst running time is
In application
Back to the problem:
The problem then requires
The problem of friendship is solvable in
Consider a slight variation of the problem: in a room there are
A query can be of two forms:
x y 1, meaning that x is friend with yx y 2, meaning that we ask if x and y are in the same group of friends at that moment in timeIn this case the solution with disjoint-set data structure is the fastest, giving a complexity of
A minimum spanning tree (MST) is a subset of the edges of a connected, edge-weighted graph that connects all the vertices together without any cycles and with the minimum possible total edge weight.
It is a way of finding the most economical way to connect a set of vertices.
A MST is not necessarily unique.
If all the weights of the edges in the graph are the same, then any spanning tree of the graph is a MST.
A MST of a graph
Kruskal's Algorithm is a greedy algorithm and it behaves as follows:
To solve the problem we use a disjoint set data structure
kruskal(G):
Set mst // empty set, store edges of G
G.sortEdges() // sort edges in ascending order of weight
for v in G.nodes()
makeSet(v) // create a disjoint set for each node
// edges are given sorted
for (u,v) in G.edges()
if find(u) != find(v) // check if (u,v) make a cycle in MST
mst.add((u,v)) // include the edge in the mst
union(u,v) // merge the set of u and v
return mst
Where:
makeSet(v) initializes a disjoint set for the vertex vfind(v) returns the representative (root) of the set that contains vunion(v,u) merges the set containing the nodes u and vTime Complexity:
The complexity depends on the sorting and on the disjoint-set operations.
makeSet(v) takes find(v) and union(u,v) are nearly constant time on average thanks to the union-by-rank and path-compression heuristics, therefore Overall the time complexity of Kruskal's algorithm in dominated by the sorting.
However, since
Prim's algorithm is a greedy algorithm used to find the minimum spanning tree (MST) of a weighted undirected graph.
The algorithm starts with an empty spanning tree.
The idea is to maintain two sets of vertices.
The first set contains the vertices already included in the MST, and the other set contains the vertices not yet included. At every step, it considers all the edges that connect the two sets and picks the minimum weight edge from these edges.
After picking the edge, it moves the other endpoint of the edge to the set containing MST.
The algorithm behaves as follows:
Consider an adjacency list of a graph adj of
Check whether the graph is bipartite or not.
A bipartite graph is a graph whose vertices can be divided into two independent sets
In other words: for every edge
We can also say that there is no edge that connects vertices of same set.
A graph is bipartite if the graph coloring is possible using only two colors and vertices in the same set have the same color.
The solution is basically an adapted version of BFS:
bipartite(List<List<Integer>> G)
n = G.length() // nuber of nodes
colors[n]
for i = 0 to n
colors[i] = -1 // every node has no color in the beginning
// frontier as in BFS
Queue q // q stores pairs: (node,color)
// needed in case G is not a connected graph
for i = 0 to n
// the current node is not colored
if colors[i] == -1
// we color the node and add it to the frontier
colors[i] = 0
q.add((i, 0))
while !q.isEmpty()
p = q.pop()
v = p.frist // current vertex
c = p.second // color of the current vertex
// iterate through the neighbors of v
for j in G.get(v)
if colors[j] == c // neighbor with same color!
return false
if colors[j] == -1 // uncolored neighbor
colors[j] = (c == 1) ? 0 : 1
q.add((j, colors[j]))
return true
Observation: if
The time complexity is
Topological sorting is a way to order the nodes in a Directed Acyclic Graph (DAG) such that for every directed edge u -> v, node u comes before node v in the ordering. In simpler terms, it's a linear ordering of vertices in such a way that for every directed edge u -> v, vertex u comes before v in the ordering.
The algorithm to compute the topological ordering of a DAG
v.f for each vertex vv.f gets valorized, the vertex become black) we insert it into a stack